package hot100.logos41To50;

import hot100.datastruct.TreeNode;

/**
 * @author logos
 * date 2025/7/14 12:02
 * @version v1.0
 * @Package hot100.logos41To50
 */
public class logos43 {

    /**
     * 43. 验证二叉搜索树
     * https://leetcode.cn/problems/validate-binary-search-tree/description/?envType=study-plan-v2&envId=top-100-liked
     */
    class Solution1 {
        private long pre = Long.MIN_VALUE;

        public boolean isValidBST(TreeNode root) {
            if (root == null) {
                return true;
            }
            if (!isValidBST(root.left)) {
                return false;
            }
            if (root.val <= pre) {
                return false;
            }
            pre = root.val;
            return isValidBST(root.right);
        }
    }

    class Solution2 {
        public static long min;

        public static long max;

        public boolean isValidBST(TreeNode root) {
            if (root == null) {
                min = Long.MAX_VALUE;
                max = Long.MIN_VALUE;
                return true;
            }
            boolean lret = isValidBST(root.left);
            long lmin = min;
            long lmax = max;
            boolean rret = isValidBST(root.right);
            long rmin = min;
            long rmax = max;
            min = Math.min(Math.min(lmin, rmin), root.val);
            max = Math.max(Math.max(rmax, lmax), root.val);
            return lret && rret && root.val > lmax && root.val < rmin;
        }
    }

}
